/**
 * 力扣198的环形版
 * 
 * 单独考虑A1即可
 * 如果取A1，则答案就是 A1 + 从3开始的线性版答案
 * 如果不取A1，答案就是 从2开始的线性版答案
 * 二者较大为最终答案 
 */

class Solution {

using Iterator = vector<int>::const_iterator;

public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(1 == n) return nums[0];
        if(2 == n) return max(nums[0], nums[1]);
        return max(nums[0] + f(nums.begin() + 2, n - 3), f(nums.begin() + 1, n - 1));       
    }

    int f(Iterator begin, int n){
        if(0 == n) return 0;
        if(1 == n) return *begin;
        if(2 == n) return max(*(begin + 1), *begin);

        vector<int> X(n, 0), Y(n, 0), D(n, 0);
        X[0] = *begin;
        Y[0] = 0;
        D[0] = X[0];

        X[1] = *(begin + 1);
        Y[1] = *(begin);
        D[1] = max(X[1], Y[1]);

        ++begin; ++begin;
        for(int i=2;i<n;++i){
            X[i] = D[i - 2] + *begin++;
            Y[i] = D[i - 1];
            D[i] = max(X[i], Y[i]);     
        }
        return D[n - 1];   
    }
};